The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
Example 1:
Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1 Output: [["Q"]]
Constraints:
1 <= n <= 9
Average Rating: 4.81 (26 votes)
Solution
Overview
A brute force solution would involve generating all possible board states with N queens. There are N2 possible squares to place the first queen, N2−1 to place the second and so on. This leads to a time complexity of O(N2N), which is far too slow. The actual number of solutions is far fewer than the number of possible board states, so we should aim to minimize our consideration of invalid board states.
Imagine if we tried to generate all board states by placing queens down one by one. For 8 queens on a normal chessboard, let's say we place the first queen on the top left (index (0, 0), or, if you are familiar with Chess, a8). Then, we place the second queen to its right (index (0, 1), or b8).
There are 62 * 61 * ... * 57 = 44,261,653,680 possible ways to place the remaining 6 queens, but we already know that every single one of them is invalid, because the first 2 queens can attack each other.
Approach: Backtracking
Intuition
We can still follow the strategy of generating board states, but we should never place a queen on a square that another queen can attack. This is a perfect problem for backtracking - place the queens one by one, and when all possibilities are exhausted, backtrack by removing a queen and placing it elsewhere.
If you're not familiar with backtracking, check out the backtracking section of our Recursion II Explore Card.
Given a board state, and a possible placement for a queen, we need a smart way to determine whether or not that placement will put the queen under attack. A queen can be attacked if another queen is on the same row, column, diagonal, or anti-diagonal.
Recall that to implement backtracking, we implement a backtrack function that makes some changes to the state, calls itself again, and then when that call returns it undoes those changes (this last part is why it's called "backtracking").
Each time our backtrack function is called, we can encode the state in the following manner:
-
To make sure that we only place 1 queen per row, we will pass an integer argument
rowintobacktrack, and will only place one queen during each call. Whenever we place a queen, we'll move onto the next row by callingbacktrackagain with the parameter valuerow + 1. -
To make sure we only place 1 queen per column, we will use a set. Whenever we place a queen, we can add the column index to this set.
The diagonals are a little trickier - but they have a property that we can use to our advantage.
- For each square on a given diagonal, the difference between the row and column indices
(row - col)will be constant. Think about the diagonal that starts from(0, 0)- the ith square has the coordinates(i, i), so the difference is always 0.
- For each square on a given anti-diagonal, the sum of the row and column indexes
(row + col)will be constant. If you were to start at the highest square in an anti-diagonal and move downwards, the row index increments by 1(row + 1), and the column index decrements by 1(col - 1). These cancel each other out.
Every time we place a queen, we should calculate the diagonal and the anti-diagonal value it belongs to. In the same way we use a set to keep track of which columns have been used, we should also have a set to keep track of which diagonals and anti-diagonals have been used. Then, we can add the values for this queen to the corresponding sets.
Algorithm
We'll create a recursive function backtrack that takes a few arguments to maintain the board state. The first parameter is the row we're going to place a queen on next, and then we will have 3 sets that track which columns, diagonals, and anti-diagonals have already had queens placed on them. Additionally, we will store the actual board so that when we find a valid solution, we can include it in our answer. The function will work as follows:
-
If the current row we are considering is equal to
n, then we have a solution. Add the current board state to a list of solutions, and return. We'll make use of a small helper function to get our board into the correct output format. -
Iterate through the columns of the current row. At each column, we will attempt to place a queen at the square
(row, col)- remember we are considering the current row through the function arguments.- Calculate the diagonal and anti-diagonal that the square belongs to. If a queen has not been placed in the column, diagonal, or anti-diagonal, then we can place a queen in this column, in the current row.
- If we can't place the queen, skip this column (move on and try the next column).
-
If we were able to place a queen, then add the queen to the board and update our 3 sets (
cols,diagonals, andantiDiagonals), and call the function again, but withrow + 1. -
The function call made in step 3 explores all valid board states with the queen we placed in step 2. Since we're done exploring that path, backtrack by removing the queen from the square - this includes removing the values we added to our sets on top of removing the
"Q"from the board.
Implementation
Complexity Analysis
Given N as the number of queens (which is the same as the width and height of the board),
-
Time complexity: O(N!)
Unlike the brute force approach, we will only place queens on squares that aren't under attack. For the first queen, we have N options. For the next queen, we won't attempt to place it in the same column as the first queen, and there must be at least one square attacked diagonally by the first queen as well. Thus, the maximum number of squares we can consider for the second queen is N−2. For the third queen, we won't attempt to place it in 2 columns already occupied by the first 2 queens, and there must be at least two squares attacked diagonally from the first 2 queens. Thus, the maximum number of squares we can consider for the third queen is N−4. This pattern continues, resulting in an approximate time complexity of N!.
While it costs O(N2) to build each valid solution, the amount of valid solutions S(N) does not grow nearly as fast as N!, so O(N!+S(N)∗N2)=O(N!)
-
Space complexity: O(N2)
Extra memory used includes the 3 sets used to store board state, as well as the recursion call stack. All of this scales linearly with the number of queens. However, to keep the board state costs O(N2), since the board is of size
N * N. Space used for the output does not count towards space complexity.
good article for a classic hard problem that should always be in our back pocket! to be honest, I was scared of even attempting this problem! but the write up helped a lot! thank you!
one of the rarest occasion of seeing a cleaner/readable code in solution section rather than from the discuss section.
great article.
O(n) Space solution:
class Solution {
private boolean[] visitedCols;
boolean[] visitedDiag, visitedAntiDiag;
private List<List<String>> solutionBoards;
private int[] queenPositions;
public List<List<String>> solveNQueens(int n) {
visitedCols = new boolean[n];
visitedDiag = new boolean[n << 1];
visitedAntiDiag = new boolean[n << 1];
queenPositions = new int[n];
solutionBoards = new ArrayList<>();
backtrack(n, 0);
return solutionBoards;
}
private void backtrack(int n, int row){
if(row == n){
fillSolutionBoard(n);
}
for(int col=0; col<n; col++){
if(!visitedCols[col]
&& !isDiagonalsVisited(row, col, n)){
queenPositions[row] = col;
if(row == n-1){
fillSolutionBoard(n);
continue;
}
visitedCols[col] = true;
markDiagonals(row, col, true, n);
backtrack(n, row+1);
queenPositions[row] = -1;
visitedCols[col] = false;
markDiagonals(row, col, false, n);
}
}
}
private boolean isDiagonalsVisited(int row, int col, int n){
int diag = row - col + (n-1);
int antiDiag = row + col;
return visitedDiag[diag] || visitedAntiDiag[antiDiag];
}
private void markDiagonals(int row, int col, boolean isVisit, int n){
int diag = row - col + (n-1);
int antiDiag = row + col;
visitedDiag[diag] = isVisit;
visitedAntiDiag[antiDiag] = isVisit;
}
private void fillSolutionBoard(int n){
List<String> solBoard = new ArrayList<>();
StringBuilder row = new StringBuilder();
for(int i=0; i<n; i++)
row.append('.');
for(int q=0; q<n; q++){
row.setCharAt(queenPositions[q], 'Q');
solBoard.add(row.toString());
row.setCharAt(queenPositions[q], '.');
}
solutionBoards.add(solBoard);
}
}
This solution is so easy-understanding and organized for the leetcode beginners!
I have real O(N) solution. (it's Kotlin)
- One int array
- Recursion with N steps deep
fun solveNQueens(n: Int): List<List<String>> {
val result = mutableListOf<MutableList<String>>()
val qs = IntArray(n)
fun move(x: Int, y: Int) {
for (i in 0 until x) {
if (qs[i] == y || x - i == Math.abs(qs[i] - y)) return
}
qs[x] = y
if (x != n - 1) {
for (i in 0 until n) {
move(x + 1, i)
}
} else {
result.add(MutableList(n) { i -> String(CharArray(n) { y -> if (qs[i] == y) 'Q' else '.' }) })
}
}
for (j in 0 until n) {
move(0, j)
}
return result
}
May 23, 2021 8:42 AM
The diagonal and anti-diagonal values don't need to be kept in sets - a single unordered set or vector is enough; the (anti-)diagonal can be deduced by column[row] -/+ row.
May 23, 2021 5:36 AM
Calculating the diagonal and antidiagonal values is actually really smart. I thought I would have to do a DFS to see if the queen attacked another queen.
I don't agree with the time complexity analysis. The backtracking algorithm doesn't just consider the correct solutions- if you look at the for loop in line17 of the python3 solution, even when the queen is not placeable, that wrong state is still considered (even though we stop our backtracking). As an example of the argument, for each correct solution, we have to reach the last row where we also consider every other column of this last row in the backtracking algorithm.
That being said, it might still be correct the time complexity is O(n!), it's just the argument is not O(correct number of solutions) and therefore O(n!).
May 22, 2021 10:21 PM
is this an NP problem?
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 05/22/2021 12:53 | Accepted | 4 ms | 7.1 MB | cpp |
xxxxxxxxxxclass Solution {public: std::vector<std::vector<std::string> > solveNQueens(int n) { std::vector<std::vector<std::string> > res; std::vector<std::string> nQueens(n, std::string(n, '.')); solveNQueens(res, nQueens, 0, n); return res; }private: void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, int row, int &n) { if (row == n) { res.push_back(nQueens); return; } for (int col = 0; col != n; ++col) if (isValid(nQueens, row, col, n)) { nQueens[row][col] = 'Q'; solveNQueens(res, nQueens, row + 1, n); nQueens[row][col] = '.'; } } bool isValid(std::vector<std::string> &nQueens, int row, int col, int &n) { //check if the column had a queen before. for (int i = 0; i != row; ++i) if (nQueens[i][col] == 'Q') return false; //check if the 45° diagonal had a queen before. for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) if (nQueens[i][j] == 'Q') return false; //check if the 135° diagonal had a queen before. for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) if (nQueens[i][j] == 'Q') return false; return true; }};


